package com.njupt.StackAndQueue;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/18 16:39
 * @Description: 739. 每日温度
 * @Version: 1.0
 */


public class DailyTemperatures {


    /**
     * 暴力解 超时
     * @param temperatures
     * @return
     */
    public static int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] result = new int[len];
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                if(temperatures[j]>temperatures[i]){
                    result[i] = j-i;
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 法二：单调栈
     * @param temperatures
     * @return
     */
    public static int[] dailyTemperatures1(int[] temperatures){
        Deque<Integer> stack = new LinkedList<>();
        int len = temperatures.length;
        int[] result = new int[len];
        if(len == 1) return result;

        stack.push(0);
        for (int i = 1; i < len; i++) {

            while (!stack.isEmpty()  && temperatures[i] > temperatures[stack.peek()]){
                result[stack.peek()] = i - stack.pop();

            }
            stack.push(i);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] temperatures = {30,40,50,60};
        int[] ints = DailyTemperatures.dailyTemperatures1(temperatures);
        System.out.println(Arrays.toString(ints));
    }
}
